package com.example.javamaday.graph;

import java.util.Stack;

/**
 * 顶点排序
 */
public class DepthFirstOrder {

    private boolean[] marked;  // 索引代表顶点，值表示当前顶点是否已经被搜索

    private Stack<Integer> reversePost; // 使用栈，存储顶点序列

    // 创建一个顶点排序对象，生成顶点线性序列
    public DepthFirstOrder(Digraph digraph) {
        this.marked = new boolean[digraph.V()];
        this.reversePost = new Stack<>();

        // 遍历图中的每一个顶点，让每个顶点作为入口，完成一次深度优先搜索
        for (int v = 0; v < digraph.V() ; v++) {
            if (!marked[v]) {
                dfs(digraph, v);
            }
        }
    }

    // 基于深度优先搜索，生成顶点线性序列
    private void dfs(Digraph digraph, int v) {
        marked[v] = true;

        for (Integer w : digraph.adj(v)) {
            if (!marked[w]) {
                dfs(digraph, w);
            }
        }

        reversePost.push(v);
    }

    // 获取顶点线性序列
    public Stack<Integer> reversePost() {
        return reversePost;
    }

}
